#include <vector>
#include <iostream>
using std::vector;
vector<int>nums={4,7,8,9,2,1,4,5,6,7,2,11,8,7,6,9,4,6,3,0};
void BubbleSort(vector<int>& nums);
void SelectionSort(vector<int>& nums);
void QuickSort(vector<int>& nums,int left,int right);
void InsertSort(vector<int>& nums);
void test_bubble(vector<int> test)
{
    BubbleSort(test);
    std::cout<<"the result of bubble sort:\n";
    for(int x:test)
        std::cout<<x<<" ";
    std::cout<<std::endl;

}
void test_selection(vector<int> test)
{
    SelectionSort(test);
    std::cout<<"the result of selection sort:\n";
    for(int x:test)
        std::cout<<x<<" ";
    std::cout<<std::endl;
}
void test_insert(vector<int> test)
{
    InsertSort(test);
    std::cout<<"the result of insert sort:\n";
    for(int x:test)
        std::cout<<x<<" ";
    std::cout<<std::endl;
}
void test_quick(vector<int> test)
{
    QuickSort(test,0,test.size()-1);
    std::cout<<"the result of quick sort:\n";
    for(int i:test)
        std::cout<<i<<" ";
    std::cout<<std::endl;
}

//冒泡排序，通过相邻元素的两两比较将最值一个个往一端移动
//本例使用固定从0开始比较，即将最值放到右边
void BubbleSort(vector<int>& nums)
{
    for(int i=0;i<nums.size()-1;i++)
    {
        for(int j=0;j<nums.size()-1-i;j++)//每次比较都是从第一位开始，从上一次最值落到的位置（右端）结束
        {
            if(nums[j]>nums[j+1])   std::swap(nums[j],nums[j+1]);//这样是把大的往右移，最后得到的是升序的数组
            //获得降序的数组：nums[j]<nums[j+1]
        }
    }
}


//选择排序，通过一次次遍历选出最值并放到开头
void SelectionSort(vector<int>& nums)
{
    int max=INT32_MIN;
    int min=INT32_MIN;
    int most;
    for(int i=0;i<nums.size()-1;i++)
    {
            max=INT32_MIN;
            min=INT32_MAX;
        for(int j=i;j<nums.size();j++)
        {
            if(nums[j]<min) //若要按降序，则nums[j]>max
            {
            min=nums[j];    //降序改成max
            most=j;
            }
        }
        std::swap(nums[i],nums[most]);
    }
}

//插入排序，从索引一开始将元素插入到前面的有序数组中（只有一个元素时视为有序数组）
void InsertSort(vector<int>& nums)
{
    for(int i=1;i<nums.size();i++)
    {
        for(int j=i;j>0;j--)
        {
            if(nums[j-1]>nums[j]) std::swap(nums[j-1],nums[j]); //将i位元素通过多次比较插入前面的有序数组中
            //if(nums[j-1]<nums[j]) std::swap(nums[j-1],nums[j]);  将小于号改成大于号，就变成了降序排列
        }
    }

}


//采用二分方法，选取一个元素，比该元素大的放右边，小的放左边，然后对该元素的左右区间做相同操作（递归）
//排列时，选择原地进行排列：选取pivot，那么该位置就空出了一个坑，设置左右指针，每次必有一个指针指向一个坑，然后将另一个指针一直移动直到遇到该排序的值将其填入坑，切换指针
void QuickSort(vector<int>& nums,int left,int right)
{
    if(left>=right) return;//结束该递归层次
    //采取选取left所在位置为”坑“的方法
    int pivot=nums[left];
    int j=right;
    int i=left;
    while(i<j)
    {
        //坑在左边，从右边开始移动
        while(nums[j]>=pivot&&i<j)    j--;  //大的留在右边，遇到小的才停
        if(i<j)   nums[i++]=nums[j];
        while(nums[i]<=pivot&&i<j)    i++;  //注意i<j判断不能少
        if(i<j)   nums[j--]=nums[i];

        //要修改升降序，只需将while()语句里的大于小于号（nums[i]和pivot比）互换即可
    }
    nums[i]=pivot;  //排序完左右要将pivot填入nums[i]
    QuickSort(nums,0,i-1);
    QuickSort(nums,j+1,right);
}





//test
int main()
{
    test_bubble(nums);
    test_selection(nums);
    test_insert(nums);
    test_quick(nums);

    std::cout<<"nums used to be:\n";
    for(int i:nums)
        std::cout<<i<<" ";
    return 0;
}